package com.zjsru.oneDay202212;

/**
 * @Author: CookLee
 * @Date: 2022/12/25
 * 放置盒子
 * 你可以把盒子放在地板上的任何地方。
 * 如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。
 * 给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。
 *
 * 1
 * 11
 * 输入：n = 3
 * 输出：3
 * 解释：数字排列是 3 个盒子的摆放位置。
 * 这些盒子放在房间的一角，对应左侧位置。
 *
 * 1
 * 21
 * 输入：n = 4
 * 输出：3
 * 解释：数字排列是 3 个盒子的摆放位置。
 * 这些盒子放在房间的一角，对应左侧位置。
 */
public class MinimumBoxes {
    
    /***
     * 贪心 ，找规律
     * */
    public int minimumBoxes(int n) {
        // cur 表示第 i 层最多可以增加多少个可放置的盒子
        int cur = 1, i = 1, j = 1;
        //表示放到第几层
        while (n > cur) {
            n -= cur;
            i++;
            cur += i;
        }
        //cur 表示在第 i 层中再添加一个接触地面的盒子时可以增加多少个可放置的盒子
        cur = 1;
        while (n > cur) {
            n -= cur;
            j++;
            cur++;
        }
        //完整的放满了前 i−1层，并且在第 i 层放置了 j 个接触地面的盒子
        return (i - 1) * i / 2 + j;
    }
    
    public static void main(String[] args) {
        MinimumBoxes minimumBoxes = new MinimumBoxes();
        int n = 3;
        System.out.println(minimumBoxes.minimumBoxes(n));
    }
}
